package NowCoder.DataStructrue.BinaryTree;
import java.util.*;

/**
 * 链接：https://www.nowcoder.com/questionTerminal/6276dbbda7094978b0e9ebb183ba37b9
 * 来源：牛客网
 *
 * 走迷宫
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
 * NowCoder最喜欢游乐场的迷宫游戏，他和小伙伴们比赛谁先走出迷宫。
 * 现在把迷宫的地图给你，你能帮他算出最快走出迷宫需要多少步吗？
 *
 * 输入描述:
 * 输入包含多组数据。
 *
 * 每组数据包含一个10*10，由“#”和“.”组成的迷宫。其中“#”代表墙；“.”代表通路。
 *
 * 入口在第一行第二列；出口在最后一行第九列。
 *
 * 从任意一个“.”点都能一步走到上下左右四个方向的“.”点。
 *
 *
 * 输出描述:
 * 对应每组数据，输出从入口到出口最短需要几步。
 * 示例1
 * 输入
 * #.########
 * #........#
 * #........#
 * #........#
 * #........#
 * #........#
 * #........#
 * #........#
 * #........#
 * ########.#
 * #.########
 * #........#
 * ########.#
 * #........#
 * #.########
 * #........#
 * ########.#
 * #........#
 * #.######.#
 * ########.#
 * 输出
 * 16
 * 30
 */
public class 走迷宫_编程_2_7_15 {
    //TODO:请根据DFS和BFS两种方法重写该题
    /**
     * DFS深度优先搜索
     */
    static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
    public static void dfs(int x, int y, char[][] maze, int[][] map){
        for(int i = 0; i < 4; i++){
            int xx = x + direction[i][0];
            int yy = y + direction[i][1];
            if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10
                    && maze[xx][yy] == '.' && map[xx][yy] > map[x][y]+1){
                map[xx][yy] = map[x][y] + 1;
                dfs(xx, yy, maze, map);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[][] maze = new char[10][10];
            int[][] map = new int[10][10];
            for(int i = 0; i < 10; i++){
                String str = sc.next();
                for(int j = 0; j < 10; j++){
                    maze[i][j] = str.charAt(j);
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
            map[0][1] = 0;
            dfs(0, 1, maze, map);
            System.out.println(map[9][8]);
        }
    }

    /**
     * BFS广度优先搜索
     */

    static int[][] direction1 = {{0,-1}, {-1,0}, {0,1}, {1,0}};
    static class Node{
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main1(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[][] maze = new char[10][10];
            int[][] map = new int[10][10];
            boolean[][] visited = new boolean[10][10];
            for(int i = 0; i < 10; i++){
                String str = sc.next();
                for(int j = 0; j < 10; j++){
                    maze[i][j] = str.charAt(j);
                    if(maze[i][j] == '#'){
                        visited[i][j] = true;
                    }
                }
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node(0, 1));
            while(!queue.isEmpty()){
                Node cur = queue.poll();
                for(int i = 0; i < 4; i++){
                    Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
                    if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10
                            && !visited[next.x][next.y]){
                        queue.offer(next);
                        map[next.x][next.y] = map[cur.x][cur.y] + 1;
                        visited[next.x][next.y] = true;
                    }
                }
            }
            System.out.println(map[9][8]);
        }
    }
/**
 * 自己写的 时间复杂度复杂，未能通过
 */
//    public static void main(String[] args){
//        Scanner sc = new Scanner(System.in);
//
//        while(sc.hasNext()){
//            String[] arr = new String[10];
//            for(int i = 0;i < 10;i++){
//                arr[i] = sc.nextLine();
//            }
//            System.out.println(minTotal(arr));
//        }
//
//
//    }
//
//    public static int minTotal(String[] arr){
//        if(arr == null || arr.length == 0){return -1;}
//        int total = 0;
//        int temp = 0;//默认从左往右走，从左往右1 ，从右往左-1 ,往前走0
//        int[][] newarr= new int[10][10];
//        for(int i = 0;i < 10;i++){
//            char[] strarr = arr[i].toCharArray();
//            for(int j = 0;j < 10;j++){
//                newarr[i][j] = totalchange(strarr[j]);
//            }
//        }
//
//        //走到这一步代表了我必然会得到一个不是0 就是 1 的二维整型数组
//        int[] totalarr = {0,1};
//        while(totalarr[0] != 9 || totalarr[1] != 8){
//            if(temp == 0 && totalarr[0] < 10 ){
//                //&& newarr[totalarr[0] + 1][totalarr[1]] == 0
//                if(newarr[totalarr[0] + 1][totalarr[1]] == 0){
//                    total++;
//                    totalarr[0]++;
//                    continue;
//                }
//            }
//            if(temp == 0){
//                temp = 1;
//            }
//
//            if(temp == 1 && totalarr[1] < 10 ){
//                //&& newarr[totalarr[0]][totalarr[1] + 1] == 0
//                if(newarr[totalarr[0]][totalarr[1] + 1] == 0){
//                    total++;
//                    totalarr[1]++;
//                    temp = 0;
//                    continue;
//                }
//            }
//
//            if(temp == 1){
//                temp = -1;
//            }
//
//            if(temp == -1 && totalarr[1] > 0 ){
//                //&& newarr[totalarr[0]][totalarr[1] - 1] == 0
//                if(newarr[totalarr[0]][totalarr[1] - 1] == 0){
//                    total++;
//                    totalarr[1]--;
//                    temp = 0;
//                    continue;
//                }
//            }
//        }
//
//        return total;
//    }
//
//    public static int totalchange(char i){
//        if(i == '#'){
//            return 1;
//        }
//        if(i == '.'){
//            return 0;
//        }
//        System.err.println("传入字符错误");
//        return -1;
//    }
}

